package xyz.naokeziteng.data_structure.graph_theory;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author hawk
 * @date 2022/10/13
 * @desc Dijkstra最短路径
 **/
public class Dijkstra {
    //源点
    private int s;
    //终点
    private int t;
    private WeightedGraph G;
    private boolean[] visited;
    //源点到每个节点的路径
    private int[] dis;
    //上一个节点的下标
    private int[] pre;


    private class Node implements Comparable<Node> {
        public int v, dis;

        public Node(int v, int dis) {
            this.v = v;
            this.dis = dis;
        }

        @Override
        public int compareTo(Node o) {
            return dis - o.dis;
        }
    }


    public Dijkstra(WeightedGraph G, int s, int t) {
        G.validateVertex(s);
        this.G = G;
        this.s = s;
        this.t = t;
        this.pre = new int[G.V()];
        Arrays.fill(pre, -1);
        this.dis = new int[G.V()];
        //填充初始距离
        Arrays.fill(dis, Integer.MAX_VALUE);
        this.visited = new boolean[G.V()];

        //优先队列
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(s, 0));

        //设置源点距离
        dis[s] = 0;
        pre[s] = s;
        while (!queue.isEmpty()) {
            //当前dis值最小的节点
            int cur = queue.remove().v;
            if (visited[cur]) {
                continue;
            }

            visited[cur] = true;
            if (cur == t) {
                break;
            }
            for (int w : G.adj(cur)) {
                if (!visited[w]) {
                    int weight = G.getWeight(cur, w) + dis[cur];
                    if (weight < dis[w]) {
                        dis[w] = weight;
                        pre[w] = cur;
                        queue.add(new Node(w, weight));
                    }
                }
            }
        }


    }

    public boolean isConnected() {
        G.validateVertex(t);
        return visited[t];
    }

    //寻找单源路径
    public String path() {
        if (!isConnected()) {
            return "没有路径...";
        }
        StringBuilder sb = new StringBuilder();
        int p = t;
        while (p != s) {
            sb.append(p).append("<--");
            p = pre[p];
        }
        return sb.append(p).toString();
    }

    public static void main(String[] args) {
        Dijkstra path = new Dijkstra(new WeightedGraph("src/main/resources/g4.txt"), 0, 6);
        System.out.println(Arrays.toString(path.dis));
        System.out.println(path.path());
    }

}
